//Given a circular integer array nums (i.e., the next element of nums[nums.lengt
//h - 1] is nums[0]), return the next greater number for every element in nums.
//
// The next greater number of a number x is the first greater number to its trav
//ersing-order next in the array, which means you could search circularly to find
//its next greater number. If it doesn't exist, return -1 for this number.
//
//
// Example 1:
//
//
//Input: nums = [1,2,1]
//Output: [2,-1,2]
//Explanation: The first 1's next greater number is 2;
//The number 2 can't find next greater number.
//The second 1's next greater number needs to search circularly, which is also 2
//.
//
//
// Example 2:
//
//
//Input: nums = [1,2,3,4,3]
//Output: [2,3,4,-1,4]
//
//
//
// Constraints:
//
//
// 1 <= nums.length <= 104
// -109 <= nums[i] <= 109
//
// Related Topics 栈
// 👍 426 👎 0


package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.Stack;

//Java：Next Greater Element II
class P503NextGreaterElementIi {
    public static void main(String[] args) {
        Solution solution = new P503NextGreaterElementIi().new Solution();
        // TO TEST
        solution.nextGreaterElements(new int[]{5, 6, 3, 4, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] nextGreaterElements1(int[] nums) {
            int[] arr = new int[nums.length];
            Stack<Integer> stack = new Stack();
            for (int i = nums.length * 2 - 1; i >= 0; i--) {
                while (!stack.isEmpty() && stack.peek() <= nums[i % nums.length]) {
                    stack.pop();
                }
                arr[i % nums.length] = stack.empty() ? -1 : stack.peek();
                stack.push(nums[i % nums.length]);
            }
            return arr;
        }
        public int[] nextGreaterElements(int[] vals) {
            int[] arr = new int[vals.length];
            int[] newVals = new int[vals.length * 2];
            // 存大的数
            System.arraycopy(vals, 0, newVals, 0, vals.length);
            System.arraycopy(vals, 0, newVals, vals.length, vals.length);
            Map<Integer, Integer> greaterMap = new HashMap<>();
            Stack<Integer> stack = new Stack<>();
            for (int i = newVals.length - 1; i >= 0; i--) {
                int ele = newVals[i];
                while (!stack.isEmpty() && ele >= stack.peek()) {
                    stack.pop();
                }
                greaterMap.put(i, stack.isEmpty() ? -1 : stack.peek());
                stack.add(ele);
            }
            for (int i = 0; i < vals.length; i++) {
                Integer index = greaterMap.get(i);
                arr[i] = index;
            }
            return arr;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
